本场链接:Codeforces Round #577
闲话:这场D就过了$263$个人(指实际比赛) 这D以后再补吧.导致前三题是手速狗的胜利.可以在本场Div2拿到前几百名.

A. Important Exam

题目大意:一共有$n$个人考了一场有$m$个题目的试卷,每个题目的分值是$a_i$,一共有$ABCDE$五种选项,选对了得到全分,选错了零分.问这群人分数的总和最多是多少.只需求出最大值,不需要求出具体方案.每个人的答题卡按一个字符串给出,依次表示他每个题选了什么选项.

数据范围:
$1 \leq n,m \leq 1000$
$1 \leq a_i \leq 1000$

显然依次考虑每个题,每个题里选选项最多的那一个就选为这个题的答案,可以使答案最大.用一个$map$计数就可以轻松过掉本题.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m;cin >> n >> m;
	vector<string> s(n + 1);
	for(int i = 1;i <= n;++i)	cin >> s[i];
    int res = 0;
    vector<int> a(m,0);
    for(int i = 0;i < m;++i)	cin >> a[i];
    for(int i = 0;i < m;++i)
    {
    	map<char,int> tb;
    	for(int j = 1;j <= n;++j)
    		++tb[s[j][i]];
    	int fres = 0;
    	for(char x = 'A';x <= 'E';++x)
    		fres = max(fres,tb[x]);
    	res += fres * a[i];
    }
    cout << res;
    return 0;
}

B. Zero Array

题目大意:有一个长度为$n$的序列$a$,每次可以选一对位置不同的两个数,使他们两个的值都减一.问能否在若干次操作之后把整个序列都变成$0$.

数据范围:
$2 \leq n \leq 10^5$
$1 \leq a_i \leq 10^9$

这个题我一开始的想法是,$1$肯定是一个特殊的元素,首先进行排序,记录下所有$1$的数量.之后从第一个非$1$的数一直往后推,这些非$1$的数不断的相减(因为排序了所以一定可以减),最后得到一个$last$表示这堆序列最终会剩下多少,再跟之前的$1$进行配对.如下:

 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int a[N];
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	ll res = 0;
	for(int i = 0;i < n;++i)	cin >> a[i];
	sort(a,a + n);
	int last = 0,onecnt = 0;
	for(int i = 0;i < n;++i)
	{
		if(a[i] == 1)	++onecnt,a[i] = 0;
		else
		{
			a[i] -= last;
			last = a[i];
			a[i] = 0;
		}
	}
	if(onecnt >= last && (onecnt - last) % 2 == 0)	cout << "YES";
	else cout << "NO";
    return 0;
}

但是这个代码错了,错的原因在于$1$可能也不是那个比较特殊的元素,比如这组数据:2 2 4,显然是让$2$和$4$进行配对,使他们都消掉,但是这个代码会直接让两个$2$进行匹配,直接剩下了$4$,这样就不对了.既然这样做行不通,肯定还是有什么性质没挖掘出来.
很明显的一点是,如果说整个序列能够消成$0$,那么他整个序列的和应该是一个偶数,反之如果是一个奇数肯定是消不完的,因为必须要两两配对,奇数会多出一个.这个和的性质就看起来非常靠谱了,不过还是过不了.在1 3这组数据下就会错判成YES.这是因为如果这个序列里的最大值特别大,大到之前所有的值的和都不够他的时候,也是不能全删成$0$的.因此还需要加入一个判断:整个序列的和不光要是一个偶数还得要去掉最大值的情况下比最大值大.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	ll res = 0;
	int maxv = 0;
	for(int i = 0;i < n;++i)
	{
		int x;cin >> x;
		res += x;
		maxv = max(maxv,x);
	}	
	if(res % 2 == 1 || (res - maxv) < maxv)	cout << "NO";
	else cout << "YES";
    return 0;
}

C. Maximum Median

题目大意;给定一个长度为$n$的序列$a$,保证$n$是一个奇数,选择一个序列里的元素并累加他$1$.你最多可以执行这个操作$k$次.问整个序列的中位数最大可以是多大.

数据范围:
$1 \leq n \leq 2 * 10^5$
$1 \leq k \leq 10^9$
$1 \leq a_i \leq 10^9$

先肯定还是排个序,既然要找中位数的话.首先前面一半的元素都是毫无意义的,对中位数没有任何影响.当前的答案应该就是现在的中位数,也就是说我得把现有的这个答案尽量扩大.但是这个扩大不能是毫无道理的,这个扩大的条件有两个:
一是无视前面的一半的元素,因为他们不影响.
二是后半段的元素(包括中位数)要扩大的一段最后都必须是相同的,之后有更大的值的话可以更大.假设最终要扩大到的值是$x$的话,那么之前比$x$小的值,就得扩大到$x$,之后的值不需要扩大,如果你扩大了反而是浪费了次数,没必要这么做.也就是让从中位数开始的一段比要扩大到的值$x$小的这一段,最终都变成$x$.

综上,答案其实就是在最多修改$k$次的前提下,问从中位数开始一段比较小的值最多修改成多大的值.这个问题是一个比较明显的二分模型,$check$就是看修改次数是多少,如果中途碰到比当前二分的答案更大的就直接退出,最后判断修改次数是否是比$k$小的,如果是的话,答案可以继续扩大反之就缩小.这里说的退出不是直接就返回一个错误,而是退出循环过程,因为后面的值既然比$x$大了,那么就跟之前说的一样不影响答案,后面的不需要修改,直接跳到修改次数是否合法的判断就行了.

注意这个题的范围还是比较大的,得开$ll$.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 2e5+7;
int a[N],n,k;
bool check(int x)
{
	ll res = 0;
	for(int i = n / 2;i < n;++i)
	{
		if(a[i] < x)	res += x - a[i];
		else break;
	}
	return res <= k;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
    for(int i = 0;i < n;++i)	scanf("%lld",&a[i]);
    if(n == 1)
    {
    	printf("%lld",a[0] + k);
    	return 0;
    }
    sort(a,a + n);
    int l = 0,r = 2e9;
    while(l < r)
    {
    	int mid = l + r + 1>> 1;
    	if(check(mid))	l = mid;
    	else r = mid - 1;
    }
    printf("%lld",l);
    return 0;
}